package com.wujunshen.algorithm.leetcode.divide.conquer;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author frank woo(吴峻申) <br>
 *     email:<a href="mailto:frank_wjs@hotmail.com">frank_wjs@hotmail.com</a> <br>
 * @date 2022/7/25 21:06<br>
 */
public class 为运算表达式设计优先级 {
  List<Integer> nums = new ArrayList<>();
  List<Character> signs = new ArrayList<>();
  Map<Integer, List<Integer>> cache = new HashMap<>();

  public List<Integer> diffWaysToCompute(String expression) {
    // 1.分出数字和符号
    int num = 0;
    int n = expression.length();
    for (int i = 0; i < n; i++) {
      char c = expression.charAt(i);
      if (Character.isDigit(c)) {
        num = num * 10 + (c - '0');
        continue;
      }

      nums.add(num);
      num = 0;
      signs.add(c);
    }
    nums.add(num);
    // 2. 分治
    return dfs(0, nums.size() - 1);
  }

  private List<Integer> dfs(int start, int end) {
    int key = start * 21 + end;
    if (cache.containsKey(key)) {
      return cache.get(key);
    }

    if (start == end) {
      return Collections.singletonList(nums.get(start));
    }

    if (start + 1 == end) {
      return Collections.singletonList(calculate(nums.get(start), signs.get(start), nums.get(end)));
    }

    List<Integer> ans = new ArrayList<>();
    for (int mid = start; mid < end; mid++) {
      List<Integer> left = dfs(start, mid);
      List<Integer> right = dfs(mid + 1, end);
      for (int a : left) {
        for (int c : right) {
          ans.add(calculate(a, signs.get(mid), c));
        }
      }
    }

    cache.put(key, ans);
    return ans;
  }

  private int calculate(int a, char b, int c) {
    if (b == '+') {
      return a + c;
    }
    if (b == '-') {
      return a - c;
    }
    return a * c;
  }
}
